package class_0919Trie;


/**
 * 前置知识：树的基本概念（比如二叉树），数组，哈希表（部分篇幅要用）。
 * 前缀树---字典树
 */
public class Trie {
    //允许ASCII码
    /*前缀树的定制：pass end */
    public static class Node{
        int pass;//路过信息。
        int end;//以当前节点结尾。
        Node[] next;
        public Node(){
            pass = 0;
            end = 0;
            next = new Node[26];
        }
        public Node(int pass){
            this.pass = pass;
        }
    }
    private Node root;
    public Trie(){
        root = new Node();
    }
    /*返回前缀树中字符串word的数量 */
    public int search(String word){
        if(word==null){
            return 0;
        }
        Node cur = root;
        int len = word.length();
        for (int i = 0,path; i < len; i++) {//从左到右遍历字符串
            path = word.charAt(i) - 'a';
            if(cur.next[path]==null){
                return 0;//路走着就断了，意味着字符串不存在
            }
            cur = cur.next[path];//继续走
        }
        return cur.end;//顺利走完循环，最后一个节点的end记录着word的次数。
    }
    /*将word插入前缀树 */
    public void insert(String word){
        //无效字符串排除
        if(word==null){
            return;
        }
        //从树的根节点出发
        Node cur = root;
        cur.pass++;//根节点的pass+1
        int len = word.length();
        for (int i = 0,path; i < len; i++) {
            path = word.charAt(i)- 'a';//找到前往的路径
            if(cur.next[path]==null){
                //若该路不存在，则新建出来
                cur.next[path] = new Node();
            }
            cur.next[path].pass++;//新节点的pass(经过次数)默认+1.
        }
        cur.end++;//循环结束，即走到重点。
    }

    /**
     * 1. 若word没插入，直接返回。不过要知道有没有出现过，必须要serach.
     * 2.若word插入过前缀树，则删除一次。
     */
    public void delete(String word){
        //从前缀树中删除字符串word

        //无效字符串或者字符串不在前缀树，->直接返回。
        if(word==null||search(word)==0){
            return;
        }

        //word已经保证存在了。
        Node cur = root;
        /*root.pass可能为负数吗？ */
        cur.pass--;//根节点处的pass-1
        int len = word.length();
        for (int i = 0, path; i < len; i++) {
            path = word.charAt(i)- 'a';
            //如果pass减为0，那么以cur.next[path]的节点后的路径不能存在了。
            --cur.next[path].pass;
            if(cur.next[path].pass==0){
                cur.next[path] = null;
                return;
            }
            cur = cur.next[path];
        }
        cur.end--;
    }

    public int prefixNumber(String prefix){
        //返回前缀树中以prefix为前缀的字符串个数。
        if(prefix==null){
            return 0;
        }
        Node cur = root;
        int len = prefix.length();
        for (int i = 0,path; i < len; i++) {
            path = prefix.charAt(i) - 'a';
            if (cur.next[path] == null) {
                return 0;//说明任何单词不以prefix作前缀。
            }
            cur = cur.next[path];
        }
        return cur.pass;//与search相同的套路， 但是返回结果是:pass!
    }
}
